|
In complexity theory, UP ("Unambiguous Non-deterministic Polynomial-time") is the complexity class of decision problems solvable in polynomial time on a non-deterministic Turing machine with at most one accepting path for each input. UP contains P and is contained in NP. A common reformulation of NP states that a language is in NP if and only if a given answer can be verified by a deterministic machine in polynomial time. Similarly, a language is in UP if a given answer can be verified in polynomial time, and the verifier machine only accepts at most ''one'' answer for each problem instance. More formally, a language ''L'' belongs to UP if there exists a two input polynomial time algorithm ''A'' and a constant c such that :if x in L , then there exists a unique certificate y with |y| = O(|x|c) such that A(x,y) = 1 :if x is not in L, there is no certificate y with |y| = O(|x|c) such that A(x,y) = 1 :Algorithm A verifies ''L'' in polynomial time. UP (and its complement co-UP) contain both the integer factorization problem and parity game problem; because determined effort has yet to find a polynomial-time solution to any of these problems, it is suspected to be difficult to show P=UP, or even P=(UP ∩ co-UP). The Valiant-Vazirani theorem states that NP is contained in RPPromise-UP, which means that there is a randomized reduction from any problem in NP to a problem in Promise-UP. UP is not known to have any complete problems. ==References== 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「UP (complexity)」の詳細全文を読む スポンサード リンク
|